import math

def euclidean_distance(point1, point2):
    return math.sqrt(sum((a - b) ** 2 for a, b in zip(point1, point2)))

def knn_predict(training_data, training_labels, test_point, k=3):
 
    if len(training_data) != len(training_labels):
        raise ValueError("训练数据和标签长度不一致")
    
    if k > len(training_data):
        raise ValueError("k值不能大于训练数据数量")

    distances = []
    for i, train_point in enumerate(training_data):
        dist = euclidean_distance(train_point, test_point)
        distances.append((training_labels[i], dist))
    
    distances.sort(key=lambda x: x[1])
    k_nearest = distances[:k]
    
    label_counts = {}
    for label, _ in k_nearest:
        if label in label_counts:
            label_counts[label] += 1
        else:
            label_counts[label] = 1
    
    max_count = 0
    predicted_label = None
    for label, count in label_counts.items():
        if count > max_count:
            max_count = count
            predicted_label = label
    
    return predicted_label

def knn_predict_all(training_data, training_labels, test_data, k=3):
    predictions = []
    for test_point in test_data:
        prediction = knn_predict(training_data, training_labels, test_point, k)
        predictions.append(prediction)
    return predictions

def main():
    training_data = [
        [1, 2], [1, 4], [2, 1], [2, 3], [3, 2],
        [6, 5], [7, 6], [8, 5], [8, 7], [7, 8]
    ]
    
    training_labels = ['A', 'A', 'A', 'A', 'A', 
                      'B', 'B', 'B', 'B', 'B']
    

    test_points = [
        [1.5, 2.5], 
        [7.5, 6.5],  
        [4, 4]      
    ]
    
    k = 3
    predictions = knn_predict_all(training_data, training_labels, test_points, k)
    
    print("K近邻算法预测结果 (k={}):".format(k))
    for i, (point, prediction) in enumerate(zip(test_points, predictions)):
        print(f"测试点 {point} -> 预测类别: {prediction}")

if __name__ == "__main__":
    main()